package com.atguigu.myzhxy;

import java.util.Scanner;

public class test {
    public static void main(String[] arg){
        Scanner sc = new Scanner(System.in);
        int num=sc.nextInt();
        System.out.println(feibo(num));
    }

    public static int feibo(int n) {
        if (n==0||n==1){
            return n;
        }
        int a=(feibo(n-1)%900000012+feibo(n-2)%900000012)%900000012;
        return a;
    }


    public static int sum(int n) {
        if (n==1){
            return 1;
        }
        if (n==2){
            return sum(n-1)+n;
        }
        for (int i=2;i<n;i++){
            if (n%i==0){//不是质数
                return sum(n-1);
            }
        }
        return sum(n-1)+n;
    }


}
